DROPS

Document

DOI: 10.4230/LIPIcs.AofA.2022.14

On the Contraction Method with Reduced Independence Assumptions

Authors: Ralph Neininger and Jasmin Straub

Published in: LIPIcs, Volume 225, 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)

Abstract

Recursive sequences of laws of random variables (and random vectors) are considered where an independence assumption which is usually made within the setting of the contraction method is dropped. This restricts the study to sequences which after normalization lead to asymptotic normality. We provide a general univariate central limit theorem which can directly be applied to problems from the analysis of algorithms and random recursive structures without further knowledge of the contraction method. Also multivariate central limit theorems are shown and bounds on rates of convergence are provided. Examples include some previously shown central limit analogues as well as new applications on Fibonacci matchings.

Cite as

Ralph Neininger and Jasmin Straub. On the Contraction Method with Reduced Independence Assumptions. In 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 225, pp. 14:1-14:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{neininger_et_al:LIPIcs.AofA.2022.14,
  author =	{Neininger, Ralph and Straub, Jasmin},
  title =	{{On the Contraction Method with Reduced Independence Assumptions}},
  booktitle =	{33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)},
  pages =	{14:1--14:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-230-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{225},
  editor =	{Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2022.14},
  URN =		{urn:nbn:de:0030-drops-161008},
  doi =		{10.4230/LIPIcs.AofA.2022.14},
  annote =	{Keywords: Probabilistic Analysis of Algorithms, random Trees, weak Convergence, Probability Metrics, Contraction Method}
}

Document

DOI: 10.4230/LIPIcs.AofA.2020.22

Convergence Rates in the Probabilistic Analysis of Algorithms

Authors: Ralph Neininger and Jasmin Straub

Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)

Abstract

In this extended abstract a general framework is developed to bound rates of convergence for sequences of random variables as they mainly arise in the analysis of random trees and divide-and-conquer algorithms. The rates of convergence are bounded in the Zolotarev distances. Concrete examples from the analysis of algorithms and data structures are discussed as well as a few examples from other areas. They lead to convergence rates of polynomial and logarithmic order. Our results show how to obtain a significantly better bound for the rate of convergence when the limiting distribution is Gaussian.

Cite as

Ralph Neininger and Jasmin Straub. Convergence Rates in the Probabilistic Analysis of Algorithms. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 22:1-22:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{neininger_et_al:LIPIcs.AofA.2020.22,
  author =	{Neininger, Ralph and Straub, Jasmin},
  title =	{{Convergence Rates in the Probabilistic Analysis of Algorithms}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{22:1--22:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-147-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{159},
  editor =	{Drmota, Michael and Heuberger, Clemens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.22},
  URN =		{urn:nbn:de:0030-drops-120529},
  doi =		{10.4230/LIPIcs.AofA.2020.22},
  annote =	{Keywords: weak convergence, probabilistic analysis of algorithms, random trees, probability metrics}
}

Search Results

Documents authored by Straub, Jasmin

On the Contraction Method with Reduced Independence Assumptions

Abstract

Cite as

Convergence Rates in the Probabilistic Analysis of Algorithms

Abstract

Cite as

Thanks for your feedback!

Could not send message